\documentclass{ctexart}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{float}
\usepackage{booktabs}

\title{4.4 Theoretical questions and Programming assignments}
\author{Shao kexin \\ student number: 3200103310}

\begin{document}
\maketitle

\section{$\uppercase\expandafter{\romannumeral1}$}
Solution:\\
$\beta = 2$\\
$477 = 1 + 2*(0 + 2*(1 + 2*(1 + 2*(1 + 2*(0  + 2*(1 + 2*(1 + 2*(1))))))))$\\
$477_{(10)} = 111011101_{(2)} = 1.11011101*2^{8}$

\section{$\uppercase\expandafter{\romannumeral2}$}
Solution:\\
$\beta = 2$\\
$\dfrac{3}{5} = \dfrac{1}{2}*(1 + \dfrac{1}{2}*(0 + \dfrac{1}{2}*(0 + \dfrac{1}{2}*(1 + \dfrac{3}{5}))))$\\
$\dfrac{3}{5}_{(10)} = 0.100110011001..._{(2)} = 1.00110011...*2^{-1}$

\section{$\uppercase\expandafter{\romannumeral3}$}
Proof:\\
$x = m_{x}*(\beta)^e, x_L = m_{x_L}*(\beta)^{e-1}, x_R = m_{x_R}*(\beta)^{e}$\\
$m_{x} = d_0 + \frac{d_1}{\beta} + \frac{d_2}{\beta^2} + ... + \frac{d_{p-1}}{\beta^{p-1}}$\\
$m_{x_L} = dl_0 + \frac{dl_1}{\beta} + \frac{dl_2}{\beta^2} + ... + \frac{dl_{p-1}}{\beta^{p-1}}$\\
$m_{x_R} = dr_0 + \frac{dr_1}{\beta} + \frac{dr_2}{\beta^2} + ... + \frac{dr_{p-1}}{\beta^{p-1}}$\\
$\because \quad x = \beta^e$\\
$\therefore \quad {d_0, d_1, d_2, ..., d_{p-1}} = {1, 0, 0, ..., 0}$\\
$\because \quad x_L, x_R adjacent to x \quad and \quad x_L < x < x_R$\\
$\therefore \quad {dl_0, dl_1, dl_2, ..., dl_{p-1}} = {\beta - 1, \beta - 1, \beta - 1, ..., \beta - 1}, {dr_0, dr_1, dr_2, ..., dr_{p-2}, dr_{p-1}} = {1, 0, 0, ..., 0, 1}$\\
$\therefore \quad x_R - x = \beta*(x - x_L)$

\section{$\uppercase\expandafter{\romannumeral4}$}
Solution:\\
$\beta = 2$\\
$x = \dfrac{3}{5} = \dfrac{1}{2}*(1 + \dfrac{1}{2}*(0 + \dfrac{1}{2}*(0 + \dfrac{1}{2}*(1 + \dfrac{3}{5}))))$\\
$x = \dfrac{3}{5}_{(10)} = 0.100110011001..._{(2)} = 1.00110011...*2^{-1}$\\
$p = 23 + 1, e \in [-126, 127]$\\
$1.00110011001100110011001*2^{-1} < x = 1.00110011...*2^{-1} < 1.00110011001100110011010*2^{-1}$\\
$x - x_L = \frac{3}{5}*2^{-24}$\\
$x_R - x_L = 2^{-24}$\\
$x_R - x = (x_R - x_L) - (x - x_L) = \frac{2}{5}*2^{-24} < x - x_L$\\
$fl(x) = x_R, roundoff = \frac{2}{5}*2^{-24}$

\section{$\uppercase\expandafter{\romannumeral5}$}
Solution:\\
$x_L < x < x_R, x_R - x_L = 2^{-24}$\\
roundoff $< \frac{x_R - x_L}{2} = 2^{-25}$

\section{$\uppercase\expandafter{\romannumeral6}$}
Solution:\\
$x = \frac{1}{4}, f(x) = 1 - cosx$\\
$1_{(10)} = 1.00000000000000000000000*2^{0}$\\
$cos(x) = 1.11110000000101010100101*2^{-1}$\\
$1 - cos(x) = 1.11111101010101101100000*2^{-6}$\\
损失了 5 bit 的精度。

\section{$\uppercase\expandafter{\romannumeral7}$}
Solution:\\
method1: $f(x) = 1 - cosx = 2*sin(x/2)$\\
method2: $\dfrac{x^2}{2!} - \dfrac{x^4}{4!} + \sum^{\infty}_{n = 1} \dfrac{(-1)^{n-1}}{(2n)!}x^{2n}$

\section{$\uppercase\expandafter{\romannumeral8}$}
$$cond_f = \dfrac{\Delta f / f}{\Delta x / x} \approx |\dfrac{f'x}{f}|$$
\subsection{$(x-1)^{\alpha}$}
$$cond_f = |\dfrac{\alpha x}{x-1}|$$
$$(cond_f)_{max} = cond_f(x \to 0, \alpha \ne 0)$$
\subsection{$lnx$}
$$cond_f = |\dfrac{1}{lnx}|$$
$$(cond_f)_{max} = cond_f(x \to 1)$$
\subsection{$e^x$}
$$cond_f = |x|$$
$$(cond_f)_{max} = cond_f(x \to \infty)$$
\subsection{$arccosx$}
$$cond_f = |\dfrac{-x}{\sqrt{1-x^2}arccos x}|$$
$$(cond_f)_{max} = cond_f(x \to \pm 1)$$

\section{$\uppercase\expandafter{\romannumeral9}$}
$$f(x) = 1 - e^{-x}, x \in [0,1]$$
\subsection{a}
Proof:\\
$$cond_f(x) = |\dfrac{xe^{-x}}{1 - e^{-x}}| = \dfrac{x}{e^x - 1}$$
$\because \quad e^x - 1 \ge x$\\
$\therefore \quad cond_f(x) \le 1$
\subsection{b}
\begin{align}
  f_A(x) &= (1 - (1 + \delta_1)e^{-x})(1 + \delta_2) \notag \\
  &= (1 + \delta_2) - (1 + \delta_1)(1 + \delta_2)e^{-x} \notag \\
  &= (1 - e^{-x})(1 + \delta_2 - \delta_1\dfrac{(1 + \delta_2)e^{-x}}{1 - e - x}) \notag \\
  &= f(x)(1 + \delta_2 - \delta_1\dfrac{(1 + \delta_2)e^{-x}}{1 - e - x}) \notag
\end{align}
$$|\delta(x)| = |\delta_2 - \delta_1\dfrac{(1+\delta_2)e^{-x}}{1-e^{-x}}| \le (1 + \dfrac{2e^{-x}}{1 - e^{-x}})\epsilon_u$$
$\varphi(x) = 1 + \dfrac{2e^{-x}}{1 - e^{-x}} \Rightarrow cond_A(x) \le \dfrac{\varphi(x)}{cond_f(x)} = \dfrac{e^x + 1}{x}$
\subsection{c}
\begin{figure}
  \centering
  \includegraphics[width=.8\textwidth]{./9c.png}
  \caption{estimate}
\end{figure}

\section{$\uppercase\expandafter{\romannumeral10}$}
$$cond_f(a) = \dfrac{1}{|r|}\sum^{n-1}_{i = 0}|a_i\dfrac{\partial r}{\partial a_i}| = \dfrac{\sum^{n-1}_{i = 0}|a_ir^i|}{nr^n + (n -1)a_{n-1}r^{n-1} + ... + a_2r^2 + a_1r}$$
$n = r, cond_f(a) \ge \dfrac{n^n}{n!}$\\
与结果相似，当$n$很大时，$f$的小扰动会对根造成巨大影响。

\section{$\uppercase\expandafter{\romannumeral11}$}
Solution:\\
$\beta = 2, p = 2, L = -1, U = 1$\\
$a = 1.0*2^0, b = 1.1*2^0 \Rightarrow \frac{a}{b} = 0.10101010...$\\
$fl(\frac{a}{b}) = 1.0*2^{-1}$\\
$|\delta| = |\dfrac{\dfrac{a}{b}-fl(\dfrac{a}{b})}{\dfrac{a}{b}}| = \dfrac{1}{4} = \epsilon_u$

\section{$\uppercase\expandafter{\romannumeral12}$}
Proof:\\
$x \in [128, 129], x_L,x_R$相邻，且$x_L \le x \le x_R$\\
$min(x_L-x_R) = 2^{-16} > 10^{-6}$\\
因此，精度不能达到$10^{-6}$

\section{$\uppercase\expandafter{\romannumeral13}$}

\section{A}
\begin{figure}
  \centering
  \includegraphics[width=.8\textwidth]{./A.png}
  \caption{f(x), g(x), h(x)}
  \label{f::01}
\end{figure}
由图\ref{f::01}可知，$f(x)$的误差最大，$h(x)$的误差最小。

\section{B}
$$\mathbb{F}: \beta = 2, p = 3, L = -1, U = +1$$
\subsection{a}
\begin{align}
  UFL(\mathbb{F}) =& \beta^L = 0.5 \notag \\
  OFL(\mathbb{F}) =& \beta^U(\beta - \beta^{1-p}) = 3.5 \notag
\end{align}
\subsection{b}
\begin{table}[htbp]
    \centering
    \begin{tabular}{cccc}
        \midrule
        $\pm 1.00 * 2^{-1}$ & $\pm 1.01 * 2^{-1}$ & $\pm 1.10 * 2^{-1}$ & $\pm 1.11 * 2^{-1}$ \\
        $\pm 1.00 * 2^{0}$  & $\pm 1.01 * 2^{0}$  & $\pm 1.10 * 2^{0}$  & $\pm 1.11 * 2^{0}$ \\
        $\pm 1.00 * 2^{1}$  & $\pm 1.01 * 2^{1}$  & $\pm 1.10 * 2^{1}$  & $\pm 1.11 * 2^{1}$ \\
        \bottomrule
    \end{tabular}
    \begin{tabular}{cccc}
        \midrule
        $\pm 0.5$ & $\pm 0.625$ & $\pm 0.75$ & $\pm 0.875$ \\
        $\pm 1$   & $\pm 1.25$  & $\pm 1.5$  & $\pm 1.75$  \\
        $\pm 2$   & $\pm 2.5$   & $\pm 3$    & $\pm 3.5$  \\
        \bottomrule
    \end{tabular}
    \caption{all numbers in $\mathbb{F}$}
    \label{ex::01}
\end{table}
表\ref{ex::01}为$\mathbb{F}$中所有规范数的二进制和十进制表示，加上0刚好25个满足书中推论4.19。
\subsection{c}
\begin{figure}
  \centering
  \includegraphics[width=.8\textwidth]{./B1.png}
  \caption{$\mathbb{F}$}
  \label{f::02}
\end{figure}
图\ref{f::02}为$\mathbb{F}$中所有规范数在数轴上画出的图。
\subsection{d}
\begin{table}[htbp]
    \centering
    \begin{tabular}{ccc}
        \midrule
        $\pm 0.01 * 2^{-1}$ & $\pm 0.10 * 2^{-1}$ & $\pm 0.11 * 2^{-1}$ \\
        \bottomrule
    \end{tabular}
    \begin{tabular}{ccc}
        \midrule
        $\pm 0.125$ & $\pm 0.25$ & $\pm 0.5$ \\
        \bottomrule
    \end{tabular}
    \caption{all the subnormal numbers of $\mathbb{F}$}
    \label{ex::02}
\end{table}
表\ref{ex::02}为$\mathbb{F}$中所有非规范数的二进制和十进制表示。
\subsection{e}
\begin{figure}
  \centering
  \includegraphics[width=.8\textwidth]{./B2.png}
  \caption{extended $\mathbb{F}$}
  \label{f::03}
\end{figure}
图\ref{f::03}为$\mathbb{F}$中所有规范数和非规范数在数轴上画出的图。
\end{document}
